package cn.xiaolang.function.data_structure;

import java.util.TreeSet;

/**
 * topK
 *
 * @author fuhw/Dean
 * @date 2020-06-08
 */
public class TopK {
    private static TreeSet<Integer> topK = new TreeSet<>((o1, o2) -> Integer.compare(o2, o1));
    private static int k = 5;

    public static void main(String[] args) {
        int[] elements = new int[]{10, 5, 13, 8, 7, 9, 19};
        for (int i = 0; i < elements.length; i++) {
            addToTop(elements[i]);
        }
        System.out.println(topK);
    }

    /**
     * 时间复杂度O(n*lg(n))
     *
     * @param ele
     */
    private static void addToTop(int ele) {
        if (k < 0) {
            return;
        }
        if (topK.isEmpty() || topK.size() < k) {
            topK.add(ele);
            return;
        }
        if (ele > topK.last()) {
            topK.pollLast();
            topK.add(ele);
        }
    }
}
